/* Copyright (c) 2000-2009, The Johns Hopkins University
 * All rights reserved.
 *
 * The contents of this file are subject to a license (the ``License'').
 * You may not use this file except in compliance with the License. The
 * specific language governing the rights and limitations of the License
 * can be found in the file ``STDUTIL_LICENSE'' found in this 
 * distribution.
 *
 * Software distributed under the License is distributed on an AS IS 
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. 
 *
 * The Original Software is:
 *     The Stdutil Library
 * 
 * Contributors:
 *     Creator - John Lane Schultz (jschultz@cnds.jhu.edu)
 *     The Center for Networking and Distributed Systems
 *         (CNDS - http://www.cnds.jhu.edu)
 */ 

#include <stdlib.h>
#include <string.h>

#include <stdutil/stdutil.h>
#include <stdutil/stderror.h>
#include <stdutil/stdhash.h>

#ifdef __cplusplus
extern "C" {
#endif

/* stdhash is a table based implementation of a dictionary data
   structure. In particular, it is an open-address, double hashing
   hashtable (ref: Sedgewick: Algorithms in C, 3rd Ed.) that maps
   non-unique keys to values. Values can be zero length which allows
   this dictionary to function as a (multi)set of keys.

   stdhash uses a key comparison function to test for key equality and
   a key hashcode function to map keys to integers.  The key
   comparison function need only return zero when two keys are
   equivalent and non-zero when they are not.

   The default cmp and hcode fcns, used when, respectively, one or
   both of the fcns is NULL, operate directly on all the bytes of the
   key type.  The default cmp fcn is a memcmp of the two keys' bytes,
   while the hcode fcn uses stdhcode_sfh (see stdutil.h), which
   computes a 32 bit hash code based on all the bytes of the key.  If
   these defaults are inappropriate for your key type (e.g. - your key
   type is just a pointer to the data that should be compared, like a
   C string, or a structure that contains padding (most do) that you
   don't always zero out, or only part of the "key" should be used for
   comparison), then you must specify appropriate fcns when you create
   the stdhash.

   ** The user must be very careful when crafting such a pair of fcns!

   (1) (cmp(k1, k2) == 0) MUST be reflexive, symmetric, and transitive
   (2) hcode(k) MUST be invariant (always the same for a particular key)
   (3) if (cmp(k1, k2) == 0) then hcode(k1) == hhcode(k2) MUST hold

   Also the user should consider the following: 

   (4) The hcodes generated by hcode should not have significant
       underlying mathematical structure to them (e.g. - all even).
       The construction of good hash fcns is a large topic.  We
       recommend you either use the defaults or use the stdhcode_*
       fcns (see stdutil.h) in constructing your own hcode fcns.

   (5) if (cmp(k1, k2) != 0) then the probability that hashcode(k1) ==
       hashcode(k2) should not be significantly more than 1 /
       2^sizeof(stdhcode) for best performance.

   (6) stdhash will consider any hcode of zero as an hcode of 1. This
       will skew the collision probabilities for keys that map to
       the hcodes 0 and 1.

   At the core of this hashtable implementation are two internal hash
   fcns:

   The first hash fcn maps a key's hashcode to the range [0, n) (where
   n is the capacity of the hashtable). This mapping is used to find
   where in the table a search for that key should begin.

   The second hash fcn returns an offset (based on the hashcode) for
   the key that is non-zero, less than and relatively prime to n.
   This offset is used to offset through the hashtable when searching
   for a particular key.

   Example: searching for a key in the table ...  First, the hashcode
   is computed for the key. Based on that, the first hash fcn returns
   an index in the table, ind, at which to begin searching for the
   key. If ind contains no key-val pair then the key does not exist in
   the table and our search is done.  If ind contains a pair and it's
   key matches the search key then our search is done. If ind contains
   a pair but it's key doesn't match the search key (i.e. either its
   hashcode or cmp return a non-match) then I examine index (ind +=
   offset) (mod n).  I continue this process until I find a key match
   or I find an empty index. Because offset is relatively prime to n,
   I can check every index in the table in this manner in n iterations
   (the sequence of indexes generated by this process for a particular
   key is called a probe sequence). However, by keeping the table
   sparsely populated the search will always terminate, and in
   practice the search will on average terminate after a constant
   number of steps.

   The first hash fcn is the hcode fcn which is then modulo'ed the
   size of the table.  We keep the size of the table a power of 2, so
   this is implemented with a fast bitwise AND operation.  Therefore,
   the first hash fcn is the lowest lg n bits of the hcode of the key.

   The second hash fcn is the highest lg(n) - 1 bits of the hcode of
   the key and the least signficant bit set to 1.  Because the lowest
   bit is set, the second hash value is odd and therefore relatively
   prime to the power of 2 table size, so it can be used to offset
   through the table.

   Because stdhash uses an open-addressing scheme, key removals are
   more complex than in other schemes. Instead of actually deleting
   the node and saying it is empty, I leave the node in its space but
   I set the cached, hashcode to an "impossible" value (0) to indicate
   that it was removed, but searchs should not terminate here. This is
   because some insert probe sequence might have depended on the
   removed node when it was inserted and so I can't simply delete the
   node. But, if a user tries to insert into the table and such an
   "inactive" node is found it can be used by the new pair being
   inserted. Leaving these nodes in the table causes still another
   problem. If the nodes still exist in the table, then the load
   factor thresholds must be modified to take this into account when
   deciding whether or not to grow, shrink, or rehash the table. If
   they didn't, the table could be filled with "inactive" nodes and
   searches might never terminate. In this implementation I track the
   number of nodes in the table by the num_nodes variable. I make
   decisions on whether to resize or rehash the table based on: size,
   num_nodes and cap_min1.

   Some more points: I cache hashcodes for keys in stdhash_nodes.
   Obviously a key should be constant, meaning that it shouldn't
   change once it is inserted in to an associative data structure. I
   depend on that fact and property 3 (above) strongly when I am
   searching for keys.

   When rehashing occurs I don't free and reallocate active nodes. I
   allocate a new table and free those inactive nodes (hcode == 0)
   that are acting only as place holders (see prior paragraphs). Then,
   all of the active nodes are inserted into the new table.
*/

#define STDHASH_IS_LEGAL(h) ((h)->table <= (h)->begin && (h)->begin <= (h)->table_end && \
			     (h)->table + ((h)->cap_min1 + 1) == (h)->table_end && \
                             (((h)->table != NULL && (h)->cap_min1 + 1 != 0) || ((h)->table == NULL && (h)->cap_min1 + 1 == 0)) && \
			     (h)->size <= (h)->num_nodes && \
			     (h)->num_nodes <= (h)->cap_min1 + 1 && \
			     (h)->ksize != 0 && \
			     ((h)->opts & ~(STDHASH_OPTS_NO_AUTO_GROW | STDHASH_OPTS_NO_AUTO_SHRINK)) == 0)

#define STDHASH_IT_IS_LEGAL(h, it) ((it)->table == (h)->table && (it)->table_end == (h)->table_end && \
				    (it)->ksize == (h)->ksize && (it)->vsize == (h)->vsize && \
				    (it)->node_pos >= (h)->begin)

#define STDHASH_IT_IS_LEGAL2(it) ((it)->table <= (it)->table_end && \
				  (it)->table <= (it)->node_pos && (it)->node_pos <= (it)->table_end && \
				  ((it)->node_pos == (it)->table_end || (!STDHASH_POS_EMPTY((it)->node_pos) && !STDHASH_POS_INACTIVE((it)->node_pos))) && \
				  (it)->ksize != 0)

#define STDIT_HASH_IS_LEGAL(it) (((it)->type_id == STDHASH_IT_ID || (it)->type_id == STDHASH_IT_KEY_ID) && STDHASH_IT_IS_LEGAL2(&(it)->impl.hash))

/* macros for table positions (stdhash_node**s) */

#define STDHASH_POS_EMPTY(node_pos)    (*(node_pos) == NULL)
#define STDHASH_POS_INACTIVE(node_pos) ((*(node_pos))->hcode == 0)

/* macros for table nodes (stdhash_node*s) (keys and values are appended onto the end of stdhash_nodes) */

#define STDHASH_NODE_SIZE(ksize, vsize) (STDARCH_PADDED_SIZE(sizeof(stdhash_node)) + STDARCH_PADDED_SIZE(ksize) + (vsize))
#define STDHASH_NKEY(node)              ((char*) (node) + STDARCH_PADDED_SIZE(sizeof(stdhash_node)))
#define STDHASH_NVAL(node, ksize)       ((char*) (node) + STDARCH_PADDED_SIZE(sizeof(stdhash_node)) + STDARCH_PADDED_SIZE(ksize))

/* macros for default comparison fcns */

#define STDHASH_DEFAULT_CMP_FCN memcmp
#define STDHASH_DEFAULT_HCODE_FCN stdhcode_sfh

/************************************************************************************************
 * stdhash_low_cmp: Compares two keys for equality.
 ***********************************************************************************************/

STDINLINE static int stdhash_low_cmp(const stdhash *h, const void *k1, const void *k2)
{
  int ret;

  if (h->cmp_fcn == NULL) {
    ret = STDHASH_DEFAULT_CMP_FCN (k1, k2, h->ksize);

  } else {
    ret = h->cmp_fcn(k1, k2);
  }

  return ret;
}

/************************************************************************************************
 * stdhash_low_hcode: Computes the hcode for a key.
 ***********************************************************************************************/

STDINLINE static stdhcode stdhash_low_hcode(const stdhash *h, const void *key)
{
  stdhcode ret;

  if (h->hcode_fcn == NULL) {
    ret = (stdhcode) STDHASH_DEFAULT_HCODE_FCN (key, h->ksize);

  } else {
    ret = h->hcode_fcn(key);
  }

  if (ret == 0) {  /* hcode of 0 is reserved for marking inactive nodes */
    ret = 1;
  }

  return ret;
}

/************************************************************************************************
 * stdhash_low_hash: Computes initial search position and offset for a hcode.
 ***********************************************************************************************/

STDINLINE static void stdhash_low_hash(stdhcode hcode, stdsize cap_min1, stdsize cap_lg,
				       stdsize *h1, stdsize *h2)
{
  /* h1 - is the lowest lg(cap) bits of hcode 
     h2 - is the highest lg(cap) bits of hcode, but the least significant bit is set to 1 
  */

  *h1 = (stdsize) (hcode & cap_min1);                                  /* [0, cap) */
  *h2 = (stdsize) ((hcode >> (sizeof(stdhcode) * 8 - cap_lg)) | 0x1);  /* (0, cap) and odd */
}

/************************************************************************************************
 * stdhash_low_next: Get the next entry.
 ***********************************************************************************************/

STDINLINE static stdhash_node **stdhash_low_next(stdhash_node ** curr_pos, stdhash_node ** end_pos) 
{
  for (++curr_pos; 
       curr_pos != end_pos && (STDHASH_POS_EMPTY(curr_pos) || STDHASH_POS_INACTIVE(curr_pos)); 
       ++curr_pos);

  return curr_pos;
}

/************************************************************************************************
 * stdhash_low_prev: Get the previous entry.
 ***********************************************************************************************/

STDINLINE static stdhash_node **stdhash_low_prev(stdhash_node ** curr_pos) 
{
  for (--curr_pos; STDHASH_POS_EMPTY(curr_pos) || STDHASH_POS_INACTIVE(curr_pos); --curr_pos);

  return curr_pos;
}

/************************************************************************************************
 * stdhash_low_clear: Make a hashtable contain zero elements.
 ***********************************************************************************************/

STDINLINE static void stdhash_low_clear(stdhash *h) 
{
  stdhash_node ** curr_pos = h->table;
  stdhash_node ** end_pos  = h->table_end;

  if (h->num_nodes == 0) {
    return;
  }

  /* loop over entire table deleteing all allocated nodes (i.e. - h->num_nodes) */

  for (; curr_pos != end_pos; ++curr_pos) {

    if (!STDHASH_POS_EMPTY(curr_pos)) {
      free(*curr_pos);
      *curr_pos = NULL;
    }
  }

  h->begin     = h->table_end;
  h->num_nodes = 0;
  h->size      = 0;
}

/************************************************************************************************
 * stdhash_low_find: Return a key lookup and its hcode.  If
 * (find_match) return only upon finding the first match or realizing
 * the key isn't in the table.  If (!find_match) return upon finding
 * the first empty position or inactive node in key's probe sequence.
 * Assumes a table has been allocated.
 ***********************************************************************************************/

STDINLINE static stdhash_node ** stdhash_low_find(const stdhash *h, stdbool find_match, 
						  const void *key, stdhcode * hcode_ptr)
{
  stdhash_node ** curr_pos;
  stdhash_node ** end_pos;
  stdhcode        hcode;
  stdsize         h1;
  stdsize         h2;

  hcode      = stdhash_low_hcode(h, key);                     /* compute hcode of key */
  *hcode_ptr = hcode;                                         /* return hcode up */

  stdhash_low_hash(hcode, h->cap_min1, h->cap_lg, &h1, &h2);  /* compute hashes of hcode */
    
  curr_pos = h->table + h1;                                   /* initial probe position */
  end_pos  = h->table_end;

  while (1) {                                                 /* search probe sequence */

    if (STDHASH_POS_EMPTY(curr_pos)) {                        /* empty -> key is not in table */
      break;
    }

    if (find_match) {                                         /* looking for a match */

      if ((*curr_pos)->hcode == hcode &&                      /* hcodes match (inactives can't) */
	  stdhash_low_cmp(h, key, STDHASH_NKEY(*curr_pos)) == 0) {  /* keys match */
	break;
      }

    } else if (STDHASH_POS_INACTIVE(curr_pos)) {              /* else looking for a hole */
      break;                                                  /* found one */
    }

    curr_pos += h2;                                           /* offset to next probe position */

    if (curr_pos >= end_pos) {                                /* wrap around */
      curr_pos = h->table + (curr_pos - end_pos);
    }
  }

  return curr_pos;
}

/************************************************************************************************
 * stdhash_low_reshash: This function is called when it has been
 * determined that the active pairs in h need to be put into a
 * different table.  It allocates an appropriately sized table, moves
 * active nodes there and frees inactive nodes from the table.
 ***********************************************************************************************/

STDINLINE static stdcode stdhash_low_rehash(stdhash *h, stdsize request_size) 
{
  stdcode         ret = STDESUCCESS;

  stdhash_node ** table;
  stdhash_node ** table_end;
  stdhash_node ** curr_pos;
  stdhash_node ** end_pos;
  stdhash_node ** search_pos;

  stdsize         new_cap;
  stdsize         new_cap_min1;
  stdsize         new_cap_lg;
  stdsize         h1;
  stdsize         h2;

  stduint64       good_cap;

  STDSAFETY_CHECK(request_size >= h->size);
  
  /* compute a good table size (power of 2) based on MAX(request_size, STDHASH_MIN_AUTO_ALLOC) */

  request_size = STDMAX(request_size, STDHASH_MIN_AUTO_ALLOC);
  good_cap     = (stdpow2_cap(request_size) << 1);          /* (>= 3, < 6) * request_size */

  if (good_cap < request_size || good_cap > STDSIZE_MAX) {  /* overflow check */
    ret = STDENOMEM;
    goto stdhash_low_rehash_end;
  }
  
  /* good_cap will make load factor w/ request_size nodes in range (1/6, 1/3] */

  new_cap      = (stdsize) good_cap;
  new_cap_lg   = (stdsize) stdlg_up(new_cap);               /* compute lg base 2 */
  new_cap_min1 = new_cap - 1;

  /* allocate a new table */

  if (new_cap != 0) {

    /* table needs to be initially full of NULL pointers */

#if (STDARCH_NULL_IS_ZERO == 1)
    if ((table = (stdhash_node**) calloc(new_cap, sizeof(stdhash_node*))) == NULL) {
      ret = STDENOMEM;
      goto stdhash_low_rehash_end;
    }

    table_end = table + new_cap;

#else
    if ((table = (stdhash_node**) malloc(new_cap * sizeof(stdhash_node*))) == NULL) {
      ret = STDENOMEM;
      goto stdhash_low_rehash_end;
    }

    table_end = table + new_cap;

    for (curr_pos = table; curr_pos != table_end; ++curr_pos) {
      *curr_pos = NULL;
    }

#endif
  } else {
    table     = NULL;
    table_end = NULL;
  }

  /* loop over 'h' free'ing inactive nodes and inserting active nodes into new table */

  for (curr_pos = h->table, end_pos = h->table_end; curr_pos != end_pos; ++curr_pos) {

    if (STDHASH_POS_EMPTY(curr_pos)) {                          /* skip empty positions */
      continue;
    }

    if (STDHASH_POS_INACTIVE(curr_pos)) {                       /* free inactive nodes */
      free(*curr_pos);

    } else {
      /* compute hash values for entry in new table, then insert in first empty position */

      stdhash_low_hash((*curr_pos)->hcode, new_cap_min1, new_cap_lg, &h1, &h2);

      for (search_pos = table + h1; !STDHASH_POS_EMPTY(search_pos); ) {
	search_pos += h2;                                       /* offset */

	if (search_pos >= table_end) {                          /* wrap around */
	  search_pos = table + (search_pos - table_end);
	}
      }

      *search_pos = *curr_pos;                                  /* insert into new table */
    }
  }

  if (h->table != NULL) {                                       /* free old table */
    free(h->table);
  }

  h->table     = table;
  h->table_end = table_end;
  h->cap_min1  = new_cap_min1;
  h->cap_lg    = new_cap_lg;
  h->num_nodes = h->size;                                       /* zero inactive nodes now */

  /* search for begin */

  h->begin = (h->size != 0 ? stdhash_low_next(h->table - 1, h->table_end) : h->table_end);

 stdhash_low_rehash_end:
  return ret;
}

/************************************************************************************************
 * stdhash_low_insert: 
 ***********************************************************************************************/

STDINLINE static stdcode stdhash_low_insert(stdhash *h, stdit *it, const stdit *b, const stdit *e, 
					    stdsize num_ins, stdbool overwrite, stdbool advance) 
{
  stdcode         ret       = STDESUCCESS;
  stdsize         hthresh   = stdhash_high_thresh(h);
  stdhash_node ** search    = NULL;  
  stdhash_node ** first_ins = NULL;
  stdit           src_it    = *b;
  stdbool         keyed     = (stdit_key_size(b) != 0);
  stdhcode        hcode;
  const void *    key;
  const void *    val;

  while (num_ins-- != 0 && (e == NULL || !stdit_eq(&src_it, e))) {

    /* check the loading factor on the table: grow/rehash if necessary */

    if (h->num_nodes >= hthresh) {                                      /* load factor too high */

      if ((h->opts & STDHASH_OPTS_NO_AUTO_GROW) != 0) {                 /* growth disallowed */
	ret = STDEACCES;
	goto stdhash_low_insert_end;
      }

      if ((ret = stdhash_low_rehash(h, h->size + 1)) != STDESUCCESS) {  /* rehash/growth failed */
	goto stdhash_low_insert_end;
      }

      hthresh = stdhash_high_thresh(h);
    }

    /* get pointers to the key and value we are about to insert */

    val = stdit_val(&src_it);
    key = (keyed ? stdit_key(&src_it) : val);

    /* look for the next insertion point */

    search = stdhash_low_find(h, overwrite, key, &hcode);

    if (STDHASH_POS_EMPTY(search)) {  /* found a truly empty hole: create+insert a new node */

      if ((*search = (stdhash_node*) malloc(STDHASH_NODE_SIZE(h->ksize, h->vsize))) == NULL) {
	ret = STDENOMEM;
	goto stdhash_low_insert_end;
      }
    
      ++h->num_nodes;                 /* increased # of nodes in table */
    }                                 /* else found a useable node */

    /* update the table's meta information */

    ++h->size;

    if (search < h->begin) {  /* insert was before begin */
      h->begin = search;
    }

    /* set the node with the new key-value pair */

    (*search)->hcode = hcode;
    memcpy(STDHASH_NKEY(*search), key, h->ksize);
    memcpy(STDHASH_NVAL(*search, h->ksize), val, h->vsize);

    /* remember first insertion */

    if (first_ins == NULL) {
      first_ins = search;
    }

    /* advance iterator if so requested */

    if (advance) {
      stdit_next(&src_it);
    }
  }

 stdhash_low_insert_end:
  if (it != NULL) {  /* at least one insertion succeeded/empty input sequence */
    it->type_id             = STDHASH_IT_ID;
    it->impl.hash.node_pos  = (first_ins != NULL ? first_ins : h->table_end);  /* point to end if no insert/overwrite occurred */
    it->impl.hash.table     = h->table;
    it->impl.hash.table_end = h->table_end;
    it->impl.hash.ksize     = h->ksize;
    it->impl.hash.vsize     = h->vsize;
  }

  return ret;
}

/************************************************************************************************
 * stdhash_construct: Construct an initially empty hashtable.
 ***********************************************************************************************/

STDINLINE stdcode stdhash_construct(stdhash *h, stdsize ksize, stdsize vsize, 
				    stdcmp_fcn kcmp, stdhcode_fcn khcode, stduint8 opts)
{
  stdcode ret = STDESUCCESS;

  if (ksize == 0 || (opts & ~(STDHASH_OPTS_NO_AUTO_GROW | STDHASH_OPTS_NO_AUTO_SHRINK)) != 0) {
    ret = STDEINVAL;
    goto stdhash_construct_fail;
  }

  h->table     = NULL;
  h->table_end = NULL;
  h->begin     = NULL;

  h->cap_min1  = (stdsize) -1;
  h->cap_lg    = (stdsize) -1;
  h->num_nodes = 0;
  h->size      = 0;

  h->ksize     = ksize;
  h->vsize     = vsize;

  h->cmp_fcn   = kcmp;
  h->hcode_fcn = khcode;

  h->opts      = opts;

  goto stdhash_construct_end;

  /* error handling and return */

 stdhash_construct_fail:
  h->ksize = 0;  /* make STDHASH_IS_LEGAL(h) false */

 stdhash_construct_end:
  return ret;
}

/************************************************************************************************
 * stdhash_copy_construct: Construct a copy of a hashtable.
 ***********************************************************************************************/

STDINLINE stdcode stdhash_copy_construct(stdhash *dst, const stdhash *src) 
{
  stdcode         ret     = STDESUCCESS;
  stdhash_node ** dst_pos = NULL;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(src) && dst != src);

  *dst = *src;

  if (src->table != NULL) {
    stdhash_node ** src_pos;
    stdhash_node ** src_end;

    /* allocate a table */

    if ((dst->table = (stdhash_node**) malloc(sizeof(stdhash_node*) * (dst->cap_min1 + 1))) == NULL) {
      ret = STDENOMEM;
      goto stdhash_copy_construct_fail;
    }

    dst->table_end = dst->table + dst->cap_min1 + 1;
    dst->begin     = dst->table + (src->begin - src->table);

    dst_pos = dst->table;
    src_pos = src->table;
    src_end = src->table_end;

    /* loop over src cloning its nodes in dst */

    for (; src_pos != src_end; ++src_pos, ++dst_pos) {

      if (STDHASH_POS_EMPTY(src_pos)) {
	*dst_pos = NULL;

      } else {

	/* alloc, init and insert a new node */

	if ((*dst_pos = (stdhash_node*) malloc(STDHASH_NODE_SIZE(dst->ksize, dst->vsize))) == NULL) {
	  ret = STDENOMEM;
	  goto stdhash_copy_construct_clean;
	}

	(*dst_pos)->hcode = (*src_pos)->hcode;
	memcpy(STDHASH_NKEY(*dst_pos), STDHASH_NKEY(*src_pos), src->ksize);
	memcpy(STDHASH_NVAL(*dst_pos, src->ksize), STDHASH_NVAL(*src_pos, src->ksize), src->vsize);
      }
    }    
  }

  goto stdhash_copy_construct_end;

  /* error handling and return */

 stdhash_copy_construct_clean:

  while (--dst_pos >= dst->table) {
    if (!STDHASH_POS_EMPTY(dst_pos)) {
      free(*dst_pos);
    }
  }

  free(dst->table);
  dst->table = NULL;

 stdhash_copy_construct_fail:
  dst->ksize = 0;  /* make STDHASH_IS_LEGAL(dst) false */

 stdhash_copy_construct_end:
  return ret;
}

/************************************************************************************************
 * stdhash_destruct: Reclaim a hash's resources and invalidate it.
 ***********************************************************************************************/

STDINLINE void stdhash_destruct(stdhash *h) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  stdhash_low_clear(h);

  if (h->table != NULL) {
    free(h->table);
    h->table = NULL;
  }

  h->ksize = 0;  /* make STDHASH_IS_LEGAL(h) false */  
}

/************************************************************************************************
 * stdhash_set_eq: Set 'dst' to have the same contents as 'src.'
 ***********************************************************************************************/

STDINLINE stdcode stdhash_set_eq(stdhash *dst, const stdhash *src)
{
  stdcode ret = STDESUCCESS;
  stdhash cpy;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(dst) && STDHASH_IS_LEGAL(src) && 
		  dst->ksize == src->ksize && dst->vsize == src->vsize &&
		  dst->cmp_fcn == src->cmp_fcn && dst->hcode_fcn == src->hcode_fcn);

  if (dst == src) {
    goto stdhash_set_eq_end;
  }

  if ((ret = stdhash_copy_construct(&cpy, src)) != STDESUCCESS) {  /* make a copy */
    goto stdhash_set_eq_end;
  }

  stdhash_swap(dst, &cpy);                                         /* swap the hashes */
  stdhash_destruct(&cpy);                                          /* destroy the old hash */

 stdhash_set_eq_end:
  return ret;
}

/************************************************************************************************
 * stdhash_swap: Make h1 reference h2's contents and vice versa.
 ***********************************************************************************************/

STDINLINE void stdhash_swap(stdhash *h1, stdhash *h2)
{
  stdhash cpy;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h1) && STDHASH_IS_LEGAL(h2) && 
		  h1->ksize == h2->ksize && h1->vsize == h2->vsize &&
		  h1->cmp_fcn == h2->cmp_fcn && h1->hcode_fcn == h2->hcode_fcn);

  STDSWAP(*h1, *h2, cpy);
}

/************************************************************************************************
 * stdhash_begin: Get an iterator to the beginning of a hash.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_begin(const stdhash *h, stdit *it) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  it->type_id             = STDHASH_IT_ID;
  it->impl.hash.node_pos  = (stdhash_node**) h->begin;
  it->impl.hash.table     = (stdhash_node**) h->table;
  it->impl.hash.table_end = (stdhash_node**) h->table_end;
  it->impl.hash.ksize     = h->ksize;
  it->impl.hash.vsize     = h->vsize;

  return it;
}

/************************************************************************************************
 * stdhash_last: Get an iterator to the last entry of a hash.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_last(const stdhash *h, stdit *it) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));
  STDBOUNDS_CHECK(h->size != 0);

  return stdit_prev(stdhash_end(h, it));
}

/************************************************************************************************
 * stdhash_end: Get an iterator to the end of a hash.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_end(const stdhash *h, stdit *it) 
{  
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  it->type_id             = STDHASH_IT_ID;
  it->impl.hash.node_pos  = (stdhash_node**) h->table_end;
  it->impl.hash.table     = (stdhash_node**) h->table;
  it->impl.hash.table_end = (stdhash_node**) h->table_end;
  it->impl.hash.ksize     = h->ksize;
  it->impl.hash.vsize     = h->vsize;

  return it;
}

/************************************************************************************************
 * stdhash_get: Get an iterator to the 'elem_num'th element of a hash.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_get(const stdhash *h, stdit *it, stdsize elem_num) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));
  STDBOUNDS_CHECK(elem_num <= h->size);

  if (elem_num <= (h->size >> 1)) {
    stdit_advance(stdhash_begin(h, it), elem_num);

  } else {
    stdit_retreat(stdhash_end(h, it), h->size - elem_num);
  }

  return it;
}

/************************************************************************************************
 * stdhash_is_begin: Return whether or not an iterator refers to the beginning of a hash.
 ***********************************************************************************************/

STDINLINE stdbool stdhash_is_begin(const stdhash *h, const stdit *it) 
{  
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && STDIT_HASH_IS_LEGAL(it) && STDHASH_IT_IS_LEGAL(h, &it->impl.hash));

  return it->impl.hash.node_pos == h->begin;
}

/************************************************************************************************
 * stdhash_is_end: Return whether or not an iterator refers to the end of a hash.
 ***********************************************************************************************/

STDINLINE stdbool stdhash_is_end(const stdhash *h, const stdit *it) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && STDIT_HASH_IS_LEGAL(it) && STDHASH_IT_IS_LEGAL(h, &it->impl.hash));

  return it->impl.hash.node_pos == h->table_end;
}

/************************************************************************************************
 * stdhash_keyed_next: Get the next entry with the same key as 'it.'
 ***********************************************************************************************/

STDINLINE stdit *stdhash_keyed_next(const stdhash *h, stdit *it) 
{
  stdhash_node ** curr_pos = it->impl.hash.node_pos;
  stdsize         h1;
  stdsize         h2;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && STDIT_HASH_IS_LEGAL(it) && 
		  STDHASH_IT_IS_LEGAL(h, &it->impl.hash) && it->impl.hash.node_pos != h->table_end);

  /* compute hash values of 'it's key */

  stdhash_low_hash((*it->impl.hash.node_pos)->hcode, h->cap_min1, h->cap_lg, &h1, &h2);

  while (1) {
    curr_pos += h2;                               /* offset in table */

    if (curr_pos >= h->table_end) {               /* wrap around */
      curr_pos = h->table + (curr_pos - h->table_end);
    }

    if (STDHASH_POS_EMPTY(curr_pos)) {            /* empty position -> no more matches */
      it->impl.hash.node_pos = h->table_end;      /* set to end */
      break;
    }

    if ((*curr_pos)->hcode == (*it->impl.hash.node_pos)->hcode &&  /* inactives can't match */
	stdhash_low_cmp(h, STDHASH_NKEY(*curr_pos), STDHASH_NKEY(*it->impl.hash.node_pos)) == 0) {
      it->impl.hash.node_pos = curr_pos;          /* match */
      break;
    }
  }

  return it;
}

/************************************************************************************************
 * stdhash_keyed_prev: Get the previous entry with the same key as 'it.'
 ***********************************************************************************************/

STDINLINE stdit *stdhash_keyed_prev(const stdhash *h, stdit *it) 
{
  stdhash_node ** curr_pos = it->impl.hash.node_pos;
  stdsize         h1;
  stdsize         h2;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && STDIT_HASH_IS_LEGAL(it) && 
		  STDHASH_IT_IS_LEGAL(h, &it->impl.hash) && it->impl.hash.node_pos != h->table_end);
  
  /* compute hash values of 'it's key */

  stdhash_low_hash((*it->impl.hash.node_pos)->hcode, h->cap_min1, h->cap_lg, &h1, &h2);

  while (1) {
    if (curr_pos == h->table + h1) {              /* on first probe sequence spot */
      it->impl.hash.node_pos = h->table_end;      /* no more matches */
      break;
    }

    curr_pos -= h2;                               /* offset in table */

    if (curr_pos < h->table) {                    /* wrap around */
      curr_pos = h->table_end - (h->table - curr_pos);
    }

    if ((*curr_pos)->hcode == (*it->impl.hash.node_pos)->hcode &&  /* inactives can't match */
	stdhash_low_cmp(h, STDHASH_NKEY(*curr_pos), STDHASH_NKEY(*it->impl.hash.node_pos)) == 0) {
      it->impl.hash.node_pos = curr_pos;          /* match */
      break;
    }
  }

  return it;
}

/************************************************************************************************
 * stdhash_size: Return the number of key-value pair elements in a hash.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_size(const stdhash *h) 
{ 
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->size; 
}

/************************************************************************************************
 * stdhash_empty: Return whether or not an array contains zero elements.
 ***********************************************************************************************/

STDINLINE stdbool stdhash_empty(const stdhash *h) 
{ 
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->size == 0; 
}

/************************************************************************************************
 * stdhash_load_lvl: The number of nodes currently in the table.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_load_lvl(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->num_nodes;
}

/************************************************************************************************
 * stdhash_high_thresh: The load beyond which the table will (try to) grow.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_high_thresh(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return ((h->cap_min1 + 1) >> 1);  /* keep load factor < 50% */
}

/************************************************************************************************
 * stdhash_low_thresh: The size at (or below) which the table will (try to) shrink.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_low_thresh(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return ((h->cap_min1 + 1) >> 3);  /* keep load factor > 12.5% */
}

/************************************************************************************************
 * stdhash_max_size: Return the theoretical max number of elements a hash can contain.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_max_size(const stdhash *h) 
{ 
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return (STDSIZE_MAX >> 2);
}

/************************************************************************************************
 * stdhash_clear: Make a hashtable contain zero elements.
 ***********************************************************************************************/

STDINLINE void stdhash_clear(stdhash *h) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  stdhash_low_clear(h);                                          /* free all nodes */

  if ((h->opts & STDHASH_OPTS_NO_AUTO_SHRINK) == 0 &&            /* if shrinking allowed */
      h->cap_min1 + 1 != STDHASH_MIN_AUTO_ALLOC &&               /* not at min alloc already */
      h->size <= stdhash_low_thresh(h)) {                        /* fallen to low cap */
    
    stdhash_low_rehash(h, h->size);                              /* 0: realloc */
  }
}

/************************************************************************************************
 * stdhash_reserve: Adjusts hash to be able to accomadate num_pairs
 * elements wo/ realloc.  Ignores all auto allocation considerations.
 ***********************************************************************************************/

STDINLINE stdcode stdhash_reserve(stdhash *h, stdsize num_pairs) 
{
  stdcode ret = STDESUCCESS;

  if (num_pairs > stdhash_high_thresh(h)) {  /* request wouldn't fit in current table */
    ret = stdhash_low_rehash(h, num_pairs);
  }

  return ret;
}

/************************************************************************************************
 * stdhash_rehash: Reallocates table to optimum size and removes all
 * inactive nodes.  Ignores all auto allocation considerations.
 ***********************************************************************************************/

STDINLINE stdcode stdhash_rehash(stdhash *h) 
{
  return stdhash_low_rehash(h, h->size);
}

/************************************************************************************************
 * stdhash_find: Lookup a key.  Return an iterator to the first
 * key-value pair that matches, end if none.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_find(const stdhash *h, stdit *it, const void *key) 
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  if (h->size != 0) {  /* size == 0 -> give end immediately; avoid special case of no table */
    stdhcode        hcode;
    stdhash_node ** search = stdhash_low_find(h, STDTRUE, key, &hcode);

    it->impl.hash.node_pos = (!STDHASH_POS_EMPTY(search) ? search : h->table_end);  /* not found */

  } else {
    it->impl.hash.node_pos = h->table_end;
  }

  it->type_id             = STDHASH_IT_ID;
  it->impl.hash.table     = h->table;
  it->impl.hash.table_end = h->table_end;
  it->impl.hash.ksize     = h->ksize;
  it->impl.hash.vsize     = h->vsize;

  return it;
}

/************************************************************************************************
 * stdhash_contains: Return whether or not a stdhash contains a key.
 ***********************************************************************************************/

STDINLINE stdbool stdhash_contains(const stdhash *h, const void *key)
{
  stdit it;

  return !stdhash_is_end(h, stdhash_find(h, &it, key));
}

/************************************************************************************************
 * stdhash_put:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_put(stdhash *h, stdit *it, const void *key, const void *val)
{
  return stdhash_put_n(h, it, key, val, 1);
}

/************************************************************************************************
 * stdhash_put_n:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_put_n(stdhash *h, stdit *it, const void *keys, const void *vals, stdsize num_put)
{
  stdit b;

  return stdhash_put_seq_n(h, it, stdit_pptr(&b, keys, vals, h->ksize, h->vsize), num_put);
}

/************************************************************************************************
 * stdhash_put_seq:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_put_seq(stdhash *h, stdit *it, const stdit *b, const stdit *e)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && (stdit_eq(b, e) || STDTRUE) &&
		  (stdit_key_size(b) == h->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == h->ksize)) &&
		  (stdit_val_size(b) == h->vsize || h->vsize == 0));

  return stdhash_low_insert(h, it, b, e, (stdsize) -1, STDTRUE, STDTRUE);
}

/************************************************************************************************
 * stdhash_put_seq_n:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_put_seq_n(stdhash *h, stdit *it, const stdit *b, stdsize num_put)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && 
		  (stdit_key_size(b) == h->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == h->ksize)) &&
		  (stdit_val_size(b) == h->vsize || h->vsize == 0));

  return stdhash_low_insert(h, it, b, NULL, num_put, STDTRUE, STDTRUE);
}

/************************************************************************************************
 * stdhash_insert:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_insert(stdhash *h, stdit *it, const void *key, const void *val)
{
  return stdhash_insert_n(h, it, key, val, 1);
}

/************************************************************************************************
 * stdhash_insert_n:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_insert_n(stdhash *h, stdit *it, const void *keys, const void *vals, stdsize num_insert)
{
  stdit b;

  return stdhash_insert_seq_n(h, it, stdit_pptr(&b, keys, vals, h->ksize, h->vsize), num_insert);
}

/************************************************************************************************
 * stdhash_insert_seq:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_insert_seq(stdhash *h, stdit *it, const stdit *b, const stdit *e)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && (stdit_eq(b, e) || STDTRUE) &&
		  (stdit_key_size(b) == h->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == h->ksize)) &&
		  (stdit_val_size(b) == h->vsize || h->vsize == 0));

  return stdhash_low_insert(h, it, b, e, (stdsize) -1, STDFALSE, STDTRUE);
}

/************************************************************************************************
 * stdhash_insert_seq_n:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_insert_seq_n(stdhash *h, stdit *it, const stdit *b, stdsize num_insert)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && 
		  (stdit_key_size(b) == h->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == h->ksize)) &&
		  (stdit_val_size(b) == h->vsize || h->vsize == 0));

  return stdhash_low_insert(h, it, b, NULL, num_insert, STDFALSE, STDTRUE);
}

/************************************************************************************************
 * stdhash_insert_rep:
 ***********************************************************************************************/

STDINLINE stdcode stdhash_insert_rep(stdhash *h, stdit *it, const void *key, const void *val, stdsize num_times)
{
  stdit b;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return stdhash_low_insert(h, it, stdit_pptr(&b, key, val, h->ksize, h->vsize), NULL, num_times, STDFALSE, STDFALSE);
}

/************************************************************************************************
 * stdhash_erase: Erase a key-value pair from a hash.
 ***********************************************************************************************/

STDINLINE void stdhash_erase(stdhash *h, stdit *it) 
{
  stdhash_node ** orig_pos;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h) && STDIT_HASH_IS_LEGAL(it) && STDHASH_IT_IS_LEGAL(h, &it->impl.hash));
  STDBOUNDS_CHECK(it->impl.hash.node_pos != h->table_end);

  orig_pos = it->impl.hash.node_pos;                             /* remember initial position */

  (*it->impl.hash.node_pos)->hcode = 0;                          /* mark node as inactive */
  it->impl.hash.node_pos = stdhash_low_next(it->impl.hash.node_pos, it->impl.hash.table_end);

  if (orig_pos == h->begin) {                                    /* update begin if necessary */
    h->begin = it->impl.hash.node_pos;
  }

  --h->size;                                                     /* update size */

  if ((h->opts & STDHASH_OPTS_NO_AUTO_SHRINK) == 0 &&            /* if shrinking allowed */
      h->cap_min1 + 1 != STDHASH_MIN_AUTO_ALLOC &&               /* not at min alloc already */
      h->size <= stdhash_low_thresh(h)) {                        /* fallen to low cap */
    
    if (stdhash_low_rehash(h, h->size) == STDESUCCESS) {         /* rehash successful */
      it->impl.hash.node_pos  = h->begin;                        /* set iterator to begin */
      it->impl.hash.table     = h->table;                        /* fill out new pointers */
      it->impl.hash.table_end = h->table_end;                    
    }
  }
}

/************************************************************************************************
 * stdhash_erase_key: Removes all key-values pairs that match key. (KISS)
 ***********************************************************************************************/

STDINLINE void stdhash_erase_key(stdhash *h, const void *key) 
{
  stdit search;

  while (!stdhash_is_end(h, stdhash_find(h, &search, key))) {
    stdhash_erase(h, &search);
  }
}

/************************************************************************************************
 * stdhash_key_size: Return the size in bytes of the keys a hash contains.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_key_size(const stdhash *h) 
{ 
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->ksize; 
}

/************************************************************************************************
 * stdhash_val_size: Return the size in bytes of the values a hash contains.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_val_size(const stdhash *h) 
{ 
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->vsize; 
}

/************************************************************************************************
 * stdhash_key_cmp: Return the fcn used for testing key equivalence.
 ***********************************************************************************************/

STDINLINE stdcmp_fcn stdhash_key_cmp(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->cmp_fcn;
}

/************************************************************************************************
 * stdhash_key_hcode: Return the fcn used for key hashcode computation.
 ***********************************************************************************************/

STDINLINE stdhcode_fcn stdhash_key_hcode(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->hcode_fcn;
}

/************************************************************************************************
 * stdhash_get_opts: Return the currently used options.
 ***********************************************************************************************/

STDINLINE stduint8 stdhash_get_opts(const stdhash *h)
{
  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  return h->opts;
}

/************************************************************************************************
 * stdhash_set_opts: Set the options on the table.
 ***********************************************************************************************/

STDINLINE stdcode stdhash_set_opts(stdhash *h, stduint8 opts)
{
  stdcode ret = STDEINVAL;

  STDSAFETY_CHECK(STDHASH_IS_LEGAL(h));

  if ((opts & ~(STDHASH_OPTS_NO_AUTO_GROW | STDHASH_OPTS_NO_AUTO_SHRINK)) == 0) {
    h->opts = opts;
    ret     = STDESUCCESS;
  }

  return ret;
}

/************************************************************************************************
 * stdhash_it_key_size: Return the size in bytes of keys 'it' references.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_it_key_size(const stdit *it) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  return it->impl.hash.ksize;
}

/************************************************************************************************
 * stdhash_it_val_size: Return the size in bytes of the values 'it' references.
 ***********************************************************************************************/

STDINLINE stdsize stdhash_it_val_size(const stdit *it) 
{  
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  return it->impl.hash.vsize;
}

/************************************************************************************************
 * stdhash_it_key: Return a pointer to the key of the key-value pair 'it' references.
 ***********************************************************************************************/

STDINLINE const void *stdhash_it_key(const stdit *it) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  return STDHASH_NKEY(*it->impl.hash.node_pos);
}

/************************************************************************************************
 * stdhash_it_val: Return a pointer to the key of the key-value pair 'it' references.
 ***********************************************************************************************/

STDINLINE void *stdhash_it_val(const stdit *it) 
{  
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  return STDHASH_NVAL(*it->impl.hash.node_pos, it->impl.hash.ksize);
}

/************************************************************************************************
 * stdhash_it_eq: Compare two iterators for equality (same pair).
 ***********************************************************************************************/

STDINLINE stdbool stdhash_it_eq(const stdit *it1, const stdit *it2) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it1) && STDIT_HASH_IS_LEGAL(it2) && 
		  it1->impl.hash.table     == it2->impl.hash.table && 
		  it1->impl.hash.table_end == it2->impl.hash.table_end && 
		  it1->impl.hash.ksize     == it2->impl.hash.ksize && 
		  it1->impl.hash.vsize     == it2->impl.hash.vsize);

  return it1->impl.hash.node_pos == it2->impl.hash.node_pos;
}

/************************************************************************************************
 * stdhash_it_next: Advance an iterator towards end by 1 position.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_it_next(stdit *it) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));
  STDBOUNDS_CHECK(it->impl.hash.node_pos != it->impl.hash.table_end);

  it->impl.hash.node_pos = stdhash_low_next(it->impl.hash.node_pos, it->impl.hash.table_end);

  return it;
}

/************************************************************************************************
 * stdhash_it_advance: Advance an iterator towards end by 'num_advance' positions.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_it_advance(stdit *it, stdsize num_advance) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  while (num_advance-- != 0) {
    STDBOUNDS_CHECK(it->impl.hash.node_pos != it->impl.hash.table_end);
    it->impl.hash.node_pos = stdhash_low_next(it->impl.hash.node_pos, it->impl.hash.table_end);
  }

  return it;
}

/************************************************************************************************
 * stdhash_it_prev: Advance an iterator towards begin by 1 position.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_it_prev(stdit *it) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));
  STDBOUNDS_CHECK(it->impl.hash.node_pos != it->impl.hash.table);      /* should be begin, but we don't track that */

  it->impl.hash.node_pos = stdhash_low_prev(it->impl.hash.node_pos);

  return it;
}

/************************************************************************************************
 * stdhash_it_retreat: Advance an iterator towards begin by 'num_retreat' positions.
 ***********************************************************************************************/

STDINLINE stdit *stdhash_it_retreat(stdit *it, stdsize num_retreat) 
{
  STDSAFETY_CHECK(STDIT_HASH_IS_LEGAL(it));

  while (num_retreat-- != 0) {
    STDBOUNDS_CHECK(it->impl.hash.node_pos != it->impl.hash.table);    /* should be begin, but we don't track that */
    it->impl.hash.node_pos = stdhash_low_prev(it->impl.hash.node_pos);
  }

  return it;
}

#ifdef __cplusplus
}
#endif
